package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月11日
*时间：下午4:36:33
*/
public class Q187 {
    /**
     * @param gas: an array of integers
     * @param cost: an array of integers
     * @return: an integer
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0 || cost == null || cost.length == 0) {
            return -1;
        }
        int length = gas.length;
        for (int i = 0; i < length; i++) {
            if (check(i, length, gas, cost)) {
                return i;
            }
        }
        return -1;
    }

    private boolean check(int i, int length, int[] gas, int[] cost) {
        int g = 0;
        int c = 0;
        for (int k = 0; k < length; k++) {
            g += gas[(i + k) % length];
            c += cost[(i + k) % length];
            if (g < c) {
                return false;
            }
        }
        return true;
    }

    @Test
    public void testA() {
        int[] gas = { 1, 1, 3, 1 };
        int[] cost = { 10, 2, 1, 1 };
        System.out.println(canCompleteCircuit(gas, cost));
    }
}
